package week4;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * 130. 被围绕的区域
 * https://leetcode-cn.com/problems/surrounded-regions/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了66.09% 的用户
 * 内存消耗：40.5 MB, 在所有 Java 提交中击败了53.81% 的用户
 * 通过测试用例：58 / 58
 * 炫耀一下:
 *
 *
 */
public class Week4SurroundedRegions {



    public void solve(char[][] board) {
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        char o = 'O';

        int columnLength = board.length;
        if(columnLength == 0) {
            return;
        }
        int rowLength = board[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for(int columnSize = 0; columnSize < columnLength; columnSize++) {
            if(board[columnSize][0] == o) {
                queue.offer(new int[]{columnSize, 0});
                board[columnSize][0] = 'A';
            }
            if(board[columnSize][rowLength - 1] == o) {
                queue.offer(new int[]{columnSize, rowLength - 1});
                board[columnSize][rowLength - 1] = 'A';
            }
        }
        for(int rowSize = 1; rowSize < rowLength - 1; rowSize++) {
            if(board[0][rowSize] == o) {
                queue.offer(new int[]{0, rowSize});
                board[0][rowSize] = 'A';
            }
            if(board[columnLength - 1][rowSize] == o) {
                queue.offer(new int[]{columnLength - 1, rowSize});
                board[columnLength - 1][rowSize] = 'A';
            }
        }

        for(;!queue.isEmpty();) {
            int[] cell = queue.poll();
            int x = cell[0];
            int y = cell[1];
            for(int size = 0; size < 4; size++) {
                int mx = x + dx[size];
                int my = y + dy[size];
                if(mx < 0 || my < 0 || mx >= columnLength || my >= rowLength || board[mx][my] != o) {
                    continue;
                }
                queue.offer(new int[]{mx, my});
                board[mx][my] = 'A';
            }
        }

        for(int columnSize = 0; columnSize < columnLength; columnSize++) {
            for(int rowSize = 0; rowSize < rowLength; rowSize++) {
                if(board[columnSize][rowSize] == 'A') {
                    board[columnSize][rowSize] = o;
                } else if(board[columnSize][rowSize] == o) {
                    board[columnSize][rowSize] = 'X';
                }
            }
        }


    }
}
